/**

   Btree.h
   =======

   Btree header

**/


#ifndef BTREE_H
#define BTREE_H


/**
   
   Includes
   --------

   - stdint.h   : standard type (uint8_t ...)
   - pthread.h  : pthread_mutex_t
   - bitfield.h : struct bitfield
   - file.h     : struct file

**/


#include <stdint.h>
#include <pthread.h>
#include <bitfield.h>
#include "file.h"


/**

   Constant: BTREE_DEGREE
   ----------------------
	
   B-Tree degree
	
**/
	
#define BTREE_DEGREE          2


/**

   Structure: struct b_node
   ------------------------
	
   B-tree node. Members are:
   - nkeys    : Number of key currently stored in node
   - keys     : Effective keys
   - is_leaf  : Boolean value telling wether node is a leaf or an internal node
   - children : Pointers to children
	
**/

struct b_node
{
  uint8_t nkeys;
  struct file* keys[2*BTREE_DEGREE-1];
  uint8_t is_leaf;
  struct b_node* children[2*BTREE_DEGREE];
};


/**

   Structure: struct b_tree
   ------------------------
	
   B-tree. Members are:
   - root    : Tree root
   - lock    : Lock for btree mutations
   - compare : compare function
   
**/

struct b_tree
{
  struct b_node* root;
  pthread_mutex_t lock;
  int (*compare)(struct file*,struct file*);
};

   


/**

   Prototypes
   ----------

**/

struct b_tree* btree_create(int (*compare)(struct file*,struct file*));
void btree_delete(struct b_tree* tree);
int btree_insert(struct b_tree* t, struct file* k);
struct file* btree_search(struct b_tree* t, struct file* k);
int btree_remove(struct b_tree* t, struct file* k);

#endif
